package leetcode.median;

/**
 * ClassName: $416_CanPartition
 * Description:
 * date: 2022-01-25 10:30
 *
 * @author liyifan
 */
public class $416_CanPartition {
    public boolean canPartition(int[] nums) {
        if (nums.length < 2)
            return false;
        int sum = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, nums[i]);
        }
        if (sum % 2 != 0)
            return false;
        int target = sum / 2;
        if (max > target)
            return false;

        boolean[] dp = new boolean[target + 1];

        dp[nums[0]] = true;
        for (int i = 1;i < nums.length;i++) {
            for (int j = target;j >= nums[i];j--) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}
